#include <iostream>
#include <queue>

using namespace std;
// 75.26 %
class Solution
{
  public:
	int numSquares(int n)
	{
		queue<pair<int, int>> q;
		q.push(make_pair(n, 0));
		vector<bool> visited(n + 1, false);
		visited[n] = true;
		while (!q.empty())
		{
			int num = q.front().first;
			int step = q.front().second;
			q.pop();
			for (int i = 1;; i++)
			{
				int a = num - i * i;
				if (a == 0)
					return step + 1;
				if (a < 0)
					break;
				if (!visited[a])
				{
					q.push(make_pair(a, step + 1));
					visited[a] = true;
				}
			}
		}
		return -1;
	}
};

int main()
{
	int n = 15;
	cout << Solution().numSquares(n) << endl;
	;
	return 0;
}
